package _interview100;

/**
 * 5. 最长回文子串
 */
public class No5 {
    private String s;
    private String[][] cache;

    public String longestPalindrome(String s) {
        this.s = s;
        int n = s.length();
        cache = new String[n][n];
        return dfs(0, n - 1);
    }

    private String dfs(int i, int j) {
        if (i > j) return "";
        else if (cache[i][j] != null) return cache[i][j];
        else if (same(i, j)) return cache[i][j] = s.substring(i, j + 1);
        else {
            String l = dfs(i + 1, j);
            String r = dfs(i, j - 1);
            return cache[i][j] = l.length() > r.length() ? l : r;
        }
    }

    private boolean same(int left, int right) {
        while (left <= right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}
